Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public TreeNode sortedArrayToBST(int[] nums) {
  12.     return build(nums, 0, nums.length - 1);
  13.   }
  15.   TreeNode build(int[] nums, int lo, int hi) {
  16.     if (lo > hi)
  17.       return null;
  19.     int mid = lo + (hi - lo) / 2;
  21.     TreeNode root = new TreeNode(nums[mid]);
  23.     root.left = build(nums, lo, mid - 1);
  24.     root.right = build(nums, mid + 1, hi);
  26.     return root;
  27.   }
  28. }